package _75

import "sort"

/*
时间复杂度：O(NC) C表示给单词按照字典序排序的时间
空间复杂度：O(N)

*/

func wordCount(startWords []string, targetWords []string) int {
	hash := make(map[string]bool)
	for _, s := range startWords {
		b := []byte(s)
		sort.Slice(b, func(i, j int) bool {
			return b[i] < b[j]
		})
		hash[string(b)] = true
	}

	ans := 0
	for _, s := range targetWords {
		b := []byte(s)
		sort.Slice(b, func(i, j int) bool {
			return b[i] < b[j]
		})
		for i := range b {
			tb := append(append([]byte(""), b[:i]...), b[i+1:]...)
			if _, ok := hash[string(tb)]; ok {
				ans++
				break
			}
		}
	}
	return ans
}
